#!/usr/bin/python



#matriz 4x4, tengo 4 ciudades 
#esta matriz, lo que indica, es para la posicion i,j
#la lista de vuelos que hay. Osea lista de vuelos desde la ciudad i a la ciudad j
#entonces por ej en [(0,1),(0,2)] estoy diciendo que hay 2 vuelos uno sale a las 
#0 y llega a las 2 y el otro sale a las 0 y llega a las 2
ciudades = [[  [] , [(0,1),(0,2)] , [ (1,3)],  [ (3,4)] , []],\
		   [  [] , []            , [(4,6)] , []        ,[]                   ],\
		   [  [] , []            , []      , []        , [(8,10)]                    ],\
		   [  [] , []            , []      , []        , [(6,8)]],\
		   [  [] , []            , []      , []        , []]  ]

#esta lista de abajo, indica la mejor hora de llegada que conozco a una ciudad.
#y desde que ciudad llego a esa hora.  La idea de la lista
#es ir  recorriendo el grafico del grafo siempre desde la hora 
#mas temprana acumulada
#https://www.youtube.com/watch?v=VENf0GXRd6E
# lo que este primero en la lista o lo que saque primero 
#sera un vuelo que me permite llegar en el menor
#tiempo posible desde un nodo ya recorrido a uno no recorrido
# (ciudad origen, hora llegada, ciudad destino)
lista = [(0,0,0)]
a  = lista.pop()
# esta es la lista que indica que nodos ya recorri
#en busqueda de cual es el menor tiempo en el que puedo llegar.
visitados = [None,None,None, None,None]


while a :
	#tomo el menor vuelo posible en cuanto a hora de llegada. 
	#que me llevara de un nodo recorrido a uno aun no recorrido
	ciudadid = a[2]
	horallegada = a[1]
	origen = a[0]

	for i in range(len(ciudades)):
		if i == ciudadid : 
			continue
		#para cada una de las ciudades que tiene vuelos con la ciudad
		#que estoy evaluando ahora.  veo si 
		#con los vuelos desde esta ciudad actual puedo llegar antes
		#del tiempo en que lo hacia antes
		for (sale,llega) in ciudades[ciudadid][i]:
			#de todos los vuelos posibles desde la ciudad actual solo 
			# puedo tener en cuenta los que salen 2 horas adelante de la hora 
			# de llegada a estaa ciudad que estoy evaluando. Como
			# tome de "lista" un vuelo que es el que mas temprano me deja en esta 
			# ciudad, entonces solo puedo evaluar los vuelos 2 horas 
			# despues a esta hora de llegada
			if horallegada+2 <= sale:
				#puedo tomar ese vuelo
				#si a esta ciudad no tenia hora de llegada, obviamente cualquiera 
				#sera mejor que nada
				if not visitados[i] :
					visitados[i] = (ciudadid,llega)
					lista.append( ( ciudadid,llega,i))
					print "actualize arriba"
				#si la hora de llegada que tenia a la ciudad de destino 
				#es mayor a la que puedo conseguir entonces reemplazo
				#por que ahora desde esta ciudad qu eestoy evaluando a la ciudadde 
				#destino llego antes entonces es una mejora
				if llega < visitados[i][1]:
					visitados[i] = (ciudadid,llega)					
					lista.append( ( ciudadid,llega,i))
					print "actualize abajo"

#				print " vuelo de %s a %s, sale a las %s llega a las %s " % (ciudadid,i,sale,llega)
	#esto en realidad ordena la lista por orden de llegada de los vuelos. 
	#esta hecho a mano por que en realidad es un heap ordenado por hora de llegada.
	# en donde si hay una ciudad que figura como destino en 2 vuelos entonces
	#se deja el mejor vuelo en la lista
	sorted(lista,lambda x,y : cmp(x[1],y[1]) )
	a = lista.pop() if len(lista) else False

#al final quedara en visitados la informacion con la mejor 
#hora de llegada a cada ciudad, y desde que otra ciudad se logra
#ese tiempo. De esta manera se puede recontruir hacia atras el recorrido
print visitados
# for i in range(len(ciudades)):
# 	for j in range(len(ciudades)):
# 			print ciudades[i][j]

#mejorHorario


# lista = (origen, horas)  //lista prioridad ordenada por horas.

# extraer primero de lista   en A
# 	# para cada vuelo partiendo de A hacia un destino X
# 	donde destino X no es alcanzable o si destino X se alcanza despues 
# 	que el vuelo que evaluo actualizar la fecha de llegada 
# 	desde A a destino X. 
# 	Si actualize horas de llegada a destino X y destino X 
# 	no fue recorrido todabia pusheo a la lista ordenada
# 	(X, hora de llegada)


# Si en la lista de destinos esta B
# el valor en horas sera el menor.


